﻿//剑指 Offer 42. 连续子数组的最大和
//输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
//要求时间复杂度为O(n)。

// 动态规划思想解

namespace LeetCode.DynamicProgramming
{
    class LeetCode_53
    {
        public class Solution
        {
            public int MaxSubArray(int[] nums)
            {
                int result = nums[0];

                for (int i = 0; i < nums.Length; i++)
                {
                    if (nums[i - 1] >= 0)
                    {
                        nums[i] = nums[i - 1] + nums[i];
                    }
                    else
                    {
                        nums[i] = nums[i - 1];
                    }
                    result = result > nums[i] ? result : nums[i];
                }

                return result;
            }
        }
    }
}
